package sort;

/**
 * Created by Administrator on 2017/3/14.
 */
public class QuickSort {
    public void sort(int[] array) {
        quickSort(array, 0, array.length - 1);
    }

    public void quickSort(int[] array, int start, int end) {
        if (start >= end) return;

        for (int i = start; i <= end; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
        int mid = partition(array, start, end);
        quickSort(array, start, mid - 1);
        quickSort(array, mid + 1, end);
    }

    private int partition(int[] array, int start, int end) {
        int left = start;
        int right = end;
        int key = array[start];
        while (left < right) {
            while (right > left && array[right] >= key) {
                right--;
            }
            array[left] = array[right];

            while (right > left && array[left] <= key) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = key;
        return left;
    }

}


